package work4;

import java.util.ArrayList;
import java.util.List;

public class Quetion3 {
	public static void main(String[] args) {
		Character[] ch = { '1', '2', '3', '4', '5', '6' };
		Permutation<Character> p = new Permutation<>(ch);
		Opt<Character> opt = new Opt<>();
		p.permutation(3, opt);
	}
}

class Opt<E> implements Permutation.Operation<E> {
	int cnt = 0;

	public void opt(List<E> list1) {
		StringBuilder str = new StringBuilder();
		for (E e : list1) {
			str.append(e);
		}
		System.out.print(str.toString() + " ");
		this.cnt++;
		if (this.cnt % 10 == 0) {
			System.out.println();
		}
	};

	public void endOpt() {
		System.out.printf("\n共%d个数\n", cnt);
	}
}

class Permutation<E> {
	private List<E> list = new ArrayList<>(0);

	public Permutation(E[] list) {
		for (E c : list) {
			this.list.add(c);
		}
	}

	// combination then all permutation
	public void permutation(int m, Operation<E> operation) {
		int n = list.size();
		int i = ~((~0) << m);
		for (all_permutation(binToList(i), m, operation); i < ~((~0) << m) << (n - m); all_permutation(binToList(i), m,
				operation)) {
			// 从右往左遍历，遇到01将其反转为10，并退出循环
			int cnt0 = 0;
			int mask = (~0);
			for (int j = 1; j < 1 << (n - 1); j <<= 1, mask <<= 1) {
				if ((i & j) == j && (i & (j << 1)) != j << 1) {
					// 01将其反转为10并将其右边所有1移至最右
					i = ((i ^ j ^ (j << 1)) & mask) | ~((~0) << cnt0);
					break;
				} else if ((i & j) == j) {
					cnt0++;
				}
			}
		}
		operation.endOpt();
	}

	private List<E> binToList(int bin) {
		List<E> relist = new ArrayList<>(0);
		for (int i = 0, j = 1; i < this.list.size(); i++, j <<= 1) {
			if ((j & bin) == j) {
				relist.add(this.list.get(i));
			}
		}
		return relist;
	}

	public void allPermutation(Operation<E> operation) {
		all_permutation(this.list, this.list.size(), operation);
		operation.endOpt();
	}

	private static <E> void all_permutation(List<E> list, int k, Operation<E> operation) {
		if (k == 1) {
			operation.opt(list);
		} else {
			all_permutation(list, k - 1, operation);
			for (int i = 1; i < k; i++) {
				swap(list, list.size() - i, list.size() - k);
				all_permutation(list, k - 1, operation);
				swap(list, list.size() - i, list.size() - k);
			}
		}
	}

	interface Operation<E> {
		public void opt(List<E> list1);

		public void endOpt();
	}

	private static <E> void swap(List<E> list, int e1, int e2) {
		E temp = list.get(e1);
		list.set(e1, list.get(e2));
		list.set(e2, temp);
	}
}
